// 最好全局声明变量，不是全局需要手动初始化
// 插入是字符转换成的数字
const int N = 5e5 + 5;
struct PAM {
	int cur, tot, lst;
	int s[N];
	struct node { int len, fail, dep, ch[26];} a[N];

	PAM() : cur(0), tot(1), lst(0) {
		a[0].fail = 1;
		a[0].len = 0; a[1].len = -1;
		s[0] = 26; // 第0个改成非法状态
	}

	int get_fail(int u) {
		while (s[cur - a[u].len - 1] != s[cur]) {
			u = a[u].fail;
		}
		return u;
	}

	void insert(int d) {
		s[++cur] = d;
		int pos = get_fail(lst);
		if (!a[pos].ch[d]) {
			tot++;
			a[tot].len = a[pos].len + 2;
			a[tot].fail = a[get_fail(a[pos].fail)].ch[d];
			a[tot].dep = a[a[tot].fail].dep + 1;
			a[pos].ch[d] = tot;
		}
		lst = a[pos].ch[d];
	}
} pam;